package threshold;

/**
 * @Author wujiaming
 * @Description TODO
 * @Date 2023-03-05 16:47
 * @Version 1.0
 * 动态规划，爬楼梯问题
 */
public class ClimbStairs {
    /**
     *递归方法的实现
     * @param n
     * @return
     */
    public int climbStairs1(int n) {
        if(n==1){return 1;}
        if(n==2){return 2;}
        return climbStairs1(n-1) + climbStairs1(n-2);
    }

    /**
     * 记忆型的递归
     * @param n
     * @return
     */
     public int climbStairsMome(int n,int[] memo) {

        if(n==1){
            memo[n] =1;
        }else if(n==2){
            memo[n]=2;
        } else{
            memo[n] = climbStairsMome(n-1,memo) + climbStairsMome(n-2,memo);
        }
         return memo[n];
    }

    public int climbStars2(int n){
        int[] memo = new int[n + 1];
        return climbStairsMome(n,memo);
    }

    /**
     * 动态规划思想，从前往后，将每一种状态结果保存在一个数组中
     * @param n
     * @return
     */
    public int climbStars3(int n){
        if (n==1){return 1;}
        if (n==2){return 2;}
        int[] dp = new int[n+1];
        dp[1] = 1;dp[2]=2;
        for (int i = 3; i <=n ; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }

    /**
     * 动态规划的升级版，迭代法
     * @param n
     * @return
     */
    public int climbStars4(int n){
        if(n==1){return 1;}
        if(n==2){return 2;}
        if(n==3){return 3;}
        int p =1,q=2,r=3;
        for (int i = 4; i <=n ; i++) {
            p = q;
            q = r;
            r = p+q;
        }
        return r;
    }

    public static void main(String[] args) {
        ClimbStairs test = new ClimbStairs();
        //递归方法
        System.out.println(test.climbStairs1(6));

        //记忆型的递归方法
        System.out.println(test.climbStars2(6));

        //动态规划思想
        System.out.println(test.climbStars3(6));

        //改进版的动态规划
         System.out.println(test.climbStars4(6));

    }
}
